#include<bits/stdc++.h>
using namespace std;
#include<stdbool.h>

typedef struct BinaryTreeNode
{
	int data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;

}BTNode;

//二叉树查找值为x的结点
BTNode* Find(BTNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* lret = Find(root->left, x);
	if (lret)
	{
		return lret;
	}
	BTNode* rret = Find(root->right, x);
	if (rret)
	{
		return rret;
	}
	return NULL;
}
BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreateTree()
{ 
	BTNode* node1 = BuyNode(2);
	BTNode* node2 = BuyNode(1);
	BTNode* node3 = BuyNode(3);
	node1->left = node2;
	node1->right = node3;
	return node1;

}
void PrevOrder(BTNode *root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	
	InOrder(root->right);
}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

int TreeSize(BTNode* root)
{
	if(root == nullptr)
    {
        return 0;
    }
    int leftSize = TreeSize(root->left);
    int rightSize = TreeSize(root->right);

    return leftSize + rightSize + 1;
}
int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);
	return left > right ? left + 1 : right + 1;

}
int TreeKLevel(BTNode* root, int k)
{
	//根的第k层个数=左子树的第k-1层个数+右子树的第k-1层个数
	if (root == NULL)
	{
		return 0;
   }
	if (k == 1)
	{
		return 1;
	}
	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}
//完全
// void PrevCreateTree(BTNode*& node,int n)
// {
//     if(n == 0)
//     {
//         node = nullptr;
//         return ;
//     }
//     int x;cin >> x;
//     node = BuyNode(x);
//     int m = n - 1;
//     int left_m = m / 2;
//     int right_m = m - left_m;
//     PrevCreateTree(node->left,left_m);
//     PrevCreateTree(node->right,right_m);
// }
void PrevCreateTree(BTNode*& node)
{
    char ch;
    do {
        ch = getchar();
    } while (isspace(ch)); 
    if(ch == '#') node = nullptr; 
    else
    {
    node = BuyNode(ch - '0');
    printf("输入左子树的值,输入#表示左子树为空\n");
    PrevCreateTree(node->left);
    printf("输入右子树的值,输入#表示右子树为空\n");
    PrevCreateTree(node->right);
    }
}

void LevelOrder(BTNode* root)
{
	queue<BTNode*> q;
	if(root != nullptr) {
		q.push(root);
	}
    int qsize = 1;
    
	while(q.size())
	{
	  for(int i = 0;i < qsize;++i)
      {
	   BTNode* t = q.front();
	   q.pop();
	   cout << t->data << ' ';
	   if(t->left) q.push(t->left);
	   if(t->right)q.push(t->right);
      }
	  cout << endl;
	  qsize = q.size(); 
	} 
	
}
void Destroy(BTNode*root)
{
    if(root == nullptr)
    {
        return ;
    }
    Destroy(root->left);
    Destroy(root->right);
    cout << root->data <<  "被销毁"<<endl; 
    free(root);
}
int main()
{
    BTNode* root = CreateTree();
    cout << TreeKLevel(root,1) << endl;
    cout << TreeKLevel(root,2) << endl;
    Destroy(root);
    return 0;
}
